
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <sstream>

#include "DataDefine.h"
#include "Solution.h"
#include "DPSolution.h"
#include "CommonSolution.h"
#include "BinaryTree.h"
#include "STLExample.h"
#include "LinkListSolution.hpp"
#include "SortSolution.hpp"
#include "Helper.h"
#include "BackTrackingSolution.hpp"

using namespace std;

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

vector<int> stringToIntegerVector(string input) {
    vector<int> output;
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    std::stringstream ss;
    ss.str(input);
    string item;
    char delim = ',';
    while (getline(ss, item, delim)) {
        output.push_back(stoi(item));
    }
    return output;
}

TreeNode* stringToTreeNode(string input) {
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    if (!input.size()) {
        return nullptr;
    }
    
    string item;
    stringstream ss;
    ss.str(input);
    
    getline(ss, item, ',');
    TreeNode* root = new TreeNode(stoi(item));
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);
    
    while (true) {
        TreeNode* node = nodeQueue.front();
        nodeQueue.pop();
        
        if (!getline(ss, item, ',')) {
            break;
        }
        
        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int leftNumber = stoi(item);
            node->left = new TreeNode(leftNumber);
            nodeQueue.push(node->left);
        }
        
        if (!getline(ss, item, ',')) {
            break;
        }
        
        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int rightNumber = stoi(item);
            node->right = new TreeNode(rightNumber);
            nodeQueue.push(node->right);
        }
    }
    return root;
}

ListNode* stringToListNode(string input) {
    // Generate list from the input
    vector<int> list = stringToIntegerVector(input);
    
    // Now convert that list into linked list
    ListNode* dummyRoot = new ListNode(0);
    ListNode* ptr = dummyRoot;
    for(int item : list) {
        ptr->next = new ListNode(item);
        ptr = ptr->next;
    }
    ptr = dummyRoot->next;
    delete dummyRoot;
    return ptr;
}

string treeNodeToString(TreeNode* root) {
    if (root == nullptr) {
        return "[]";
    }
    
    string output = "";
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        
        if (node == nullptr) {
            output += "null, ";
            continue;
        }
        
        output += to_string(node->val) + ", ";
        q.push(node->left);
        q.push(node->right);
    }
    return "[" + output.substr(0, output.length() - 2) + "]";
}

void prettyPrintLinkedList(string notes, ListNode* node)
{
    cout << notes << ":";
    while (node && node->next) {
        cout << node->val << "->";
        node = node->next;
    }
    
    if (node) {
        cout << node->val << endl;
    } else {
        cout << "Empty LinkedList" << endl;
    }
}

void prettyPrintTree(TreeNode* node, string prefix = "", bool isLeft = true) {
    if (node == nullptr) {
        cout << "Empty tree";
        return;
    }
    
    if(node->right) {
        prettyPrintTree(node->right, prefix + (isLeft ? "│   " : "    "), false);
    }
    
    cout << prefix + (isLeft ? "└── " : "┌── ") + to_string(node->val) + "\n";
    
    if (node->left) {
        prettyPrintTree(node->left, prefix + (isLeft ? "    " : "│   "), true);
    }
}

// 最短路径为，到子节点的路径
// 如果左子树为空，右子树不为空则返回左子树的最小深度 + 1
// 如果右子树为空，左子树不为空则返回右子树的最小深度 + 1
// 如果左子树，右子树都为空，则返回 0 + 1
// 如果左子树和右子树多不为空，则返回两个子树中的最小值+1
int getminDepth(TreeNode* root)
{
    //    if(root == nullptr)
    //        return 0;
    //    if(root->left == nullptr)
    //        return getminDepth(root->right) + 1;
    //    if(root->right == nullptr)
    //        return getminDepth(root->left) + 1;
    //
    //    int left = getminDepth(root->left);
    //    int right = getminDepth(root->right);
    //    return min(left , right) + 1;
    if(root == nullptr)
        return 0;
    if(root->left == nullptr && root->right == nullptr)
        return 1;
    int left= getminDepth(root->left);
    int right= getminDepth(root->right);
    
    if(root->left == nullptr || root->right == nullptr)
        return left + right + 1;
    return min(left, right) + 1;
}

int getMaxDepth(TreeNode* root)
{
    if(root == nullptr)
        return 0;
    int left = getMaxDepth(root->left);
    int right = getMaxDepth(root->right);
    return max(left, right) + 1;
}

template <class T>
void printfVectorVector(string notes, vector<vector<T>> &result)
{
    size_t size = result.size();
    cout << notes << ":";
    cout << "\n{\n";
    for(int i=0;i<size;i++)
    {
        cout << "{";
        size_t sizesize = result[i].size();
        for(int k=0;k<sizesize;k++)
        {
            cout << result[i][k] << ",";
        }
        cout << "}" << endl;
    }
    cout << "}" << endl;
}


void dosimpleMain();
void doLeetCodeBinaryTreeInput();
void doLeetCodeLinkListInput();
void doSortSolution();

int main(int argc, char **argv) {
    cout << "Hello Leet Code Boy..." << std::endl;
    const int wantnum = 5;
    for (int i = 0; i < wantnum; i++) {
        cout << "I Want to Change My Life,我要改变我的生活..." << endl;
    }
    dosimpleMain();
    // doLeetCodeBinaryTreeInput();
    // doLeetCodeLinkListInput();
    // doSortSolution();
    return 0;
}

void dosimpleMain()
{
    STLExample example;
    example.containerExample();
    example.randomExample();
    
    vector<int> input{3,4,2,12,5,9,0,-2,10};
    SortSolution ss;
    ss.sortQuick(input);
    printfVector("quick sort", input);
    
    myshuffle(input);
    printfVector("shuffle", input);
    ss.sortMerge(input);
    printfVector("merge sort", input);
    
    myshuffle(input);
    ss.sortBubble(input);
    printfVector("bubble sort", input);
   
    myshuffle(input);
    ss.sortSelection(input);
    printfVector("select sort", input);
    
    myshuffle(input);
    ss.sortSelection(input);
    printfVector("insertion sort", input);
    
    myshuffle(input);
    ss.sortShell(input);
    printfVector("shell sort", input);
    
    myshuffle(input);
    ss.sortwithpriority_queue(input, true);
    printfVector("priority queue ascend order", input);
    
    myshuffle(input);
    ss.sortwithpriority_queue(input, false);
    printfVector("priority queue descend order", input);
    
    myshuffle(input);
    printfVector("before sort", input);
    ss.sortHeap(input, true);
    printfVector("ascend order", input);
    
    myshuffle(input);
    ss.sortHeap(input, false);
    printfVector("descend order", input);
    
    BackTrackingSolution bs;
    vector<string> permutationstr = bs.permutation("abc");
    printfVector("permutationstr:", permutationstr);
    
    string casestr = "3[z]2[2[y]pq4[2[jk]e1[f]]]ef";
    // casestr = "2[sd2[2[f]]]";
    CommonSolution cs;
    string decodestr = cs.decodeString(casestr);
    cout << "decodestring:" << decodestr << endl;
}

void doSortSolution()
{
    SortSolution ss;
    // vector<int> input{2,1,43,5,43,467,6,7,9,8,5654543,5423,324,32,4,3,24,325,32};
    // ss.sortMerge(input);
    
    // vector<int> input{2,1,43,5,43,467,6,7,9,8,5654543,5423,324,32,4,3,24,325,32};
    vector<int> input{10,8,7,12,19,5};
    ListNode* head = buildList(input);
    printList("merge Sort before:", head);
    // head = ss.sortMerge(head);
    printList("merge sort Top-to-Bottom After:", head);
    
    LinkListSolution ls;
    // head = nullptr;
//    head = ls.insertnode(head, 0);
//    printList("insert 0:", head);
//
//    head = ls.insertnode(head, 103);
//    printList("insert 103:", head);
    
    head = ls.insertnode(head, 4);
    printList("insert 4:", head);

    SortSolution sortss;
    head = sortss.sortInsertion(head);
    printList("sort Insertion list:", head);
}

void doLeetCodeLinkListInput()
{
    LinkListSolution solution;
    
    string line;
    while (getline(cin, line))
    {
        ListNode* head = stringToListNode(line);
        prettyPrintLinkedList("Input ", head);
        
//        head = solution.reverseList(head);
//        prettyPrintLinkedList("Output",head);
        
        vector<int> result;
        solution.reversePrint(head, result);
        printfVector("reverse print", result);
        
        head = solution.reverseListRecursion(head);
        prettyPrintLinkedList("Output", head);
    }
}

void doLeetCodeBinaryTreeInput()
{
    string line;
    while (getline(cin, line))
    {
        // ListNode* head = stringToListNode(line);
        // TreeNode* ret = Solution().sortedListToBST(head);
        
        TreeNode* ret =stringToTreeNode(line);
        string out = treeNodeToString(ret);
        cout << out << endl;
        prettyPrintTree(ret);
        
        Solution solution;
        string str;
        str = solution.serialize(ret);
        cout << "serialize:" << str << endl;
        
        TreeNode* deserializeRoot = solution.deserializeTree(str);
        prettyPrintTree(deserializeRoot);
        
        vector<vector<int>> vvresult;
        solution.getallPathNodes(ret, vvresult);
        printfVectorVector("all tree paths", vvresult);
        
        vector<string> strvector;
        solution.getallPathNodesString(ret, strvector);
        printfVector("all string path", strvector);
        
        string strresult = solution.tree2str(ret);
        cout << "tree string:" << strresult << endl;
        
        vvresult.clear();
        solution.levelorderwithpreorder(ret, 1, vvresult);
        printfVectorVector("level order:", vvresult);
        
        strvector.clear();
        solution.findDuplicateSubTree(ret);
        
        string stringtree = solution.getstringTreewithlevel(ret, 0);
        cout << "tree level:" << stringtree << endl;
        
        vector<int> intresult;
        // solution.getallvaluehelper(stringtree, intresult);
        // printfVector("all node value:", intresult);
        // TreeNode* recoverroot = solution.recoverFromPreorderlevel(stringtree);
        // prettyPrintTree(recoverroot);
        
        TreeNode* recoverroot = solution.recoverFromPreorder(stringtree);
        prettyPrintTree(recoverroot);
        
        stringtree = solution.getstringTreewithlevel(recoverroot, 0);
        cout << "tree level:" << stringtree << endl;
        
        // dynamic programing
        DPSolution dpsolution;
        
        for(int i=1;i<=30;i++)
        {
            int value001 = dpsolution.climbStairsN(i);
            int value002 = dpsolution.climStairNMethod(i);
            cout << "value001:" << value001 << ",value002:" << value002 << endl;
        }
        
        for(int i=4;i<=5;i++)
        for(int j=6;j<=7;j++)
        {
            int value001 = dpsolution.gridTraveler(i, j);
            int value002 = dpsolution.gridTravelerwithDPFunction(i, j);
            cout << "grid traveler -> value001:" << value001 << ",value002:" << value002 << endl;
        }
        
        BinaryTreeBST bstsolution;
        bstsolution.splitBST(ret, 6);
        
        // serialize algorithm
        string strret = bstsolution.serialize(ret);
        cout << "serialize:" << strret << endl;
        TreeNode* nodeRet = bstsolution.deserialize(strret);
        prettyPrintTree(nodeRet);
        
        vector<vector<int>> vvv = bstsolution.BSTSequences(ret);
        
    
    }
}
